# -*- coding: utf-8 -*-

"""剑指 Offer II 021. 删除链表的倒数第 n 个结点
给定一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

示例 1：
输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]

示例 2：
输入：head = [1], n = 1
输出：[]

示例 3：
输入：head = [1,2], n = 1
输出：[1]

提示：
链表中结点的数目为 sz
1 <= sz <= 30
0 <= Node.val <= 100
1 <= n <= sz"""

# Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


class Solution:
    """本身我开始用的先扫描一趟，拿到总长度，再判断倒数第 n 个节点，从头节点需要多少步。看进阶要求，扫描一趟，猜测双指针，但是怎么也想不到用双指针扫描一次的方案。
    后面看题解，用的一个前后指针，前后指针节点差便为 n 。然后两个指针一起向后，当前指针到达尾部时，后指针也就到达合理的节点了。妙啊，看来双指针的用法变化万千"""
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        head = ListNode(next=head)
        front, behind = head, head

        while n > 0:
            front = front.next
            n -= 1
        
        while True:
            if front.next:
                front = front.next
                behind = behind.next
            else:
                break
        
        behind.next = behind.next.next

        return head.next


def gen_list_node(li):
    ln = ListNode()
    tail = ln
    for ele in li:
        tail.next = ListNode(ele)
        tail = tail.next
    return ln.next


def show_ln(ln):
    p = ln
    while True:
        if p:
            print(p.val, end=', ')
            p = p.next
        else:
            break
    print('')

if __name__ == '__main__':
    so = Solution()
    show_ln(so.removeNthFromEnd(gen_list_node([1,2,3,4,5]), 2))
    show_ln(so.removeNthFromEnd(gen_list_node([1]), 1))
    show_ln(so.removeNthFromEnd(gen_list_node([1,2]), 1))
